package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-15
 */

/**
 * 给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。
 * 你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
 *
 * 给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。
 */
public class leetcode576 {
    int maxMove;
    int[][][] cache;
    int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        this.maxMove = maxMove;
        cache = new int[m][n][maxMove + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= maxMove; k++) {
                    cache[i][j][k] = -1;
                }
            }
        }
        return dfs(m,n,0,startRow,startColumn);
    }

    public int dfs(int m,int n,int move,int x,int y){
        if (x<0 || x>=m || y<0 || y>=n) {
            return 1;
        }
        if (move>=maxMove) return 0;
        if (cache[x][y][move]!=-1) return cache[x][y][move];
        int ans = 0;
        for (int[] d : dir) {
            int newX = x+d[0];
            int newY = y+d[1];
            ans += dfs(m,n,move+1,newX,newY);
            ans %= (int)1e9+7;
        }
        cache[x][y][move] = ans;
        return ans;
    }
}
